Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

  1. "3+2*2" = 7
  2. " 3/2 " = 1
  3. " 3+5 / 2 " = 5

Note: Do not use the eval built-in library function.

Solution:

  1. public class Solution {
  2.   public int calculate(String s) {
  3.     if (s == null || s.length() == 0)
  4.       return 0;
  6.     s = "+" + s + "+";
  7.     char sign = '+';
  8.     char[] a = s.toCharArray();
  9.     int n = s.length(), res = 0, num = 0;
  10.     Stack<Integer> stack = new Stack<Integer>();
  12.     for (int i = 0; i < n; i++) {
  13.       if (Character.isDigit(a[i]))
  14.         num = num * 10 + a[i] - '0';
  16.       if (isOperator(a[i])) {
  17.         if (sign == '+') stack.push(num);
  18.         if (sign == '-') stack.push(-num);
  19.         if (sign == '*') stack.push(stack.pop() * num);
  20.         if (sign == '/') stack.push(stack.pop() / num);
  22.         num = 0;
  24.         sign = a[i];
  25.       }
  26.     }
  28.     for (int i : stack) 
  29.       res += i;
  31.     return res;
  32.   }
  34.   boolean isOperator(char c) {
  35.     return c == '+' || c == '-' || c == '*' || c == '/';
  36.   }
  37. }